package com.linchong.dynamicprogramming.medium;

import java.util.Arrays;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-26 14:24
 * @Description: Backpack$背包问题-lintCode92
 *
 * 给定n个物品，重量分别是正整数A0,A1,A2,...,An-1
 * 一个背包最大承重是正整数M
 * 最多能带走多重的物品
 *
 * eg:
 *  输入：4个物品，重量为2,3,5,7,最大承重是11
 *  输出：10,(三个物品，2,3,5)
 *
 *
 * 【解析】
 *  给定n个物品，重量分别是正整数A0,A1,A2,...,An-1
 *
 *
 *  给定n个物品，重量分别是正整数A0,A1,A2,...,An-1
 *         - 一个背包最大承重是M
 *         - 物品重量都是整数
 *         - 每个装物品的方案的总重量都是0到M
 *         - 对于某个总总量，我们能知道有没有方案能做到，就可以解决
 *
 *        注意：背包问题中，数组大小和承重有关
 *
 *    step 1:确定状态
 *          最后一步：需要直到N个物品是否能拼出重量为W(W=0,1,2,...,M)
 *                  最后一步：最后一个物品（重量为An-1）是否进入背包
 *
 *           情况一：如果前N-1个物品能拼出W,当前N个商品也能拼出W
 *           情况二：如果前N-1个物品能够拼出W-An-1,再加上最后的物品An-1,拼出W
 *
 *          子问题：
 *              要求前N个物品能不能拼出重量0,1,2,...,M
 *              需要知道前N-1个物品能不能拼出M,如果可以，则可以；如果不可以，加上最后一个重量判断
 *          状态：设f[i][w]=前i个物品能否拼出重量w（true/false）
 *
 *          常见误区：
 *              设f[i]表示前i个物品能拼出的最大重量（不超过target）
 *              反例：A=[3,9,5,2],Target=10
 *              错误原因：最优策略中，前N-1个物品拼出的不一定是不超过Target的最大重量
 *
 *           注意：背包问题要把总承重放入状态
 *     step 2:转移方程
 *          设f[i][w] = 能否用前i个物品拼出重量w（true/false）
 *              f[i][w] = f[i-1][w] or f[i-1][w-A_(i-1)]
 *     能否用前i个物品拼出重量w  能否用前i-1个物品拼出重量w  能否用前i-1个物品拼出w-A(i-1),在加上第i个物品
 *
 *     step 3:初始条件和边界情况：
 *          初始条件：
 *              f[0][0]=true:0个物品可以拼出重量0
 *              f[0][1..M]=false:0个物品不能拼出大于0的重量
 *          边界情况：
 *              f[i-1][w-A(i-1)]只能在w>=A(i-1)时使用
 *
 *     step 4:计算顺序
 *          初始化f[0][0],f[0][1],...,f[0][M]
 *          计算前1个物品能拼出那些重量：f[1][0],f[1][1],...,f[1][M]
 *          计算前2个物品能拼出那些重量：f[2][0],f[2][1],...,f[2][M]
 *          ...
 *          计算前N个物品能拼出那些重量：f[N][0],f[N][1],...,f[N][M]
 *
 *      时间复杂度：O(MN),空间复杂度：数组大小，优化后可以为O(M)
 */
public class Backpack {


	int backPack(int[] item,int m){
		int n = item.length;
		if(n ==0){
			return 0;
		}

		boolean[][] f = new boolean[n+1][m+1];
		int i,j;
		// init
		f[0][0] = true;
		for (i = 1; i <= m; i++) {
			f[0][i] = false;
		}

		// f[i][w] = f[i-1][w] or f[i-1][w-A_(i-1)]
		for(i=1;i<=n;i++){
			for(j=0;j<=m;j++){
				// 前i-1可以拼出的
				f[i][j] = f[i-1][j];
				if(j>=item[i-1]){
					f[i][j] = f[i][j] || f[i-1][j-item[i-1]];
				}
			}
		}

		//最大带走重量
		for (i = m;  i>=0 ; i--) {
			if(f[n][i]){
				return i;
			}
		}
		return 0;
	}

	public static void main(String[] args) {
		int[] item = {2,3,5};
		int m = 10;
		Backpack instance = new Backpack();
		System.out.println(instance.backPack(item,m));
	}

}
